package 力扣日常刷题.木22一月.第10天0118;

/**
 * @author 帅小伙
 * @date 2022/1/18
 * @description
 */
public class Demo16动态规划中等字符串的好分割数目 {


    public static void main(String[] args) {
        Demo16动态规划中等字符串的好分割数目 test = new Demo16动态规划中等字符串的好分割数目();

        test.numSplits("aaaaa");
    }

    public int numSplits(String s) {
        int n = s.length();
        int[] left = new int[n + 2];
        int[] right = new int[n + 2];
        boolean[] recLeft = new boolean[26];
        boolean[] recRight = new boolean[26];
        //左边字符的个数
        for (int i = 1; i <= n; i++) {
            int c = s.charAt(i - 1) - 'a';
            if (recLeft[c]) {  // 当前字符在左边存在
                left[i] = left[i - 1];
            } else {
                recLeft[c] = true;
                left[i] = left[i - 1] + 1;
            }
        }

        for (int i = n; i > 0; i--) {
            int c = s.charAt(i - 1) - 'a';
            if (recRight[c]) {
                right[i] = right[i+1];
            } else {
                recRight[c] = true;
                right[i] = right[i+1]+1;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if(left[i] == right[i+1]){
                ans++;
            }
        }
        return ans;
    }


}
